﻿#pragma once
#include <vector>
#include <map>
#include <queue>
#include <functional>

namespace matrix
{
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, MAX_W, Direction> Self;
	public:
		Graph() = default;
		// 图的创建
		// 1、IO输入
		// 2、图结构关系写到文件，读取文件
		// 3、手动添加边
		Graph(const V* a, size_t n)
		{
			_vertexs.resize(n);
			for (size_t i = 0; i < n; i++)
			{
				// _vertexs.push_back(a[i]);
				_vertexs[i] = a[i];
				_indexMap[a[i]] = i;
			}

			_matrix.resize(n);
			for (size_t i = 0; i < n; i++)
				_matrix[i].resize(n, MAX_W);
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}

		void _AddEdge(size_t srci, size_t dsti, const W& w)
		{
			_matrix[srci][dsti] = w;
			// 无向图
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}

		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			_AddEdge(srci, dsti, w);
		}

		void Print()
		{
			// 打印顶点和下标映射关系
			cout << "  ";
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				cout << i << " ";
			}
			cout << endl;
			// 打印矩阵
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				cout << i << " ";
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (_matrix[i][j] != MAX_W)
						cout << _matrix[i][j] << " ";
					else
						cout << "∞" << " ";
				}
				cout << endl;
			}
			cout << endl << endl;
			// 打印所有的边
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						cout << _vertexs[i] << "-" << _vertexs[j] << ":" <<
							_matrix[i][j] << endl;
					}
				}
			}
		}

		void BFS(const V& src)
		{
			size_t n = _vertexs.size();
			size_t srci = GetVertexIndex(src);

			// 队列和标记数组
			queue<size_t> q;
			vector<bool> vis(n, false);

			q.push(srci);
			vis[srci] = true;
			size_t levelSize = 1;

			while (!q.empty())
			{
				for (size_t i = 0; i < levelSize; ++i)
				{
					size_t front = q.front();
					q.pop();

					cout << front << ":" << _vertexs[front] << " ";
					// 把front顶点的邻接顶点入队列
					for (size_t j = 0; j < n; j++)
					{
						if (_matrix[front][j] != MAX_W && vis[j] == false)
						{
							q.push(j);
							vis[j] = true;
						}
					}
				}
				cout << endl;
				levelSize = q.size();
			}
			cout << endl;
		}

		void _DFS(size_t srci, vector<bool> vis)
		{
			cout << srci << ":" << _vertexs[srci] << endl;
			vis[srci] = true;

			// 找一个srci相邻的没有访问过的点，去往深度遍历
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				if (_matrix[srci][i] != MAX_W && vis[i] == false)
				{
					_DFS(i, vis);
				}
			}
		}

		void DFS(const V& src)
		{
			size_t srci = GetVertexIndex(src);
			vector<bool> vis(_vertexs.size(), false);

			_DFS(srci, vis);
		}

		struct Edge
		{
			size_t _srci;
			size_t _dsti;
			W _w;

			Edge(size_t srci, size_t dsti, const W& w)
				: _srci(srci)
				, _dsti(dsti)
				, _w(w)
			{}

			bool operator>(const Edge& e) const
			{
				return _w > e._w;
			}
		};

		W Kruskal(Self& minTree)
		{
			size_t n = _vertexs.size();

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			// 选出n-1条边
			int size = 0;
			W totalW = W();
			UnionFindSet ufs(n);
			while (!minque.empty())
			{
				Edge minE = minque.top();
				minque.pop();

				if (!ufs.InSet(minE._srci, minE._dsti))
				{
					cout << _vertexs[minE._srci] << "->" 
						<< _vertexs[minE._dsti] 
						<< ":" << minE._w << endl;
					minTree._AddEdge(minE._srci, minE._dsti, minE._w);
					ufs.Union(minE._srci, minE._dsti);
					++size;
					totalW += minE._w;
				}
			}
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		W Prim(Self& minTree, const V& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			vector<bool> Y(n, true);
			Y[srci] = false;

			// 从X->Y集合中连接的边里面选出最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			// 先把srci连接的边添加到队列中
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			size_t size = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge minE = minq.top();
				minq.pop();

				// 最小边目标在集合中才进行选择，否则会有回路问题
				if (Y[minE._dsti])
				{
					minTree._AddEdge(minE._srci, minE._dsti, minE._w);
					Y[minE._dsti] = false;
					++size;
					totalW += minE._w;
					if (size == n - 1)
						break;

					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[minE._dsti][i] != MAX_W)
						{
							minq.push(Edge(minE._dsti, i, _matrix[minE._dsti][i]));
						}
					}
				}
			}
			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			for (size_t i = 0; i < n; ++i)
			{
				if (i != srci)
				{
					// 找出i顶点的路径
					vector<int> path;
					size_t parenti = i;
					while (parenti != srci)
					{
						path.push_back(parenti);
						parenti = pPath[parenti];
					}
					path.push_back(srci);
					reverse(path.begin(), path.end());

					for (auto index : path)
					{
						cout << _vertexs[index] << "->";
					}
					cout << dist[i] << endl;
				}
			}
		}

		// vector<W> dist,记录srci-其他顶点最短路径权值数组
		// vector<int> pPath 记录srci-其他顶点最短路径父顶点数组
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			dist.resize(n, MAX_W);
			pPath.resize(n, -1);

			dist[srci] = 0;
			pPath[srci] = srci;

			// 已经确定最短路径的顶点集合
			vector<bool> S(n, false);

			for (size_t i = 0; i < n; ++i)
			{
				// 选最短路径顶点且该顶点未确定，更新其他路径
				size_t u = 0;
				W minE = MAX_W;
				for (size_t j = 0; j < n; j++)
				{
					if (S[j] == false && dist[j] < minE)
					{
						u = j;
						minE = dist[j];
					}
				}

				S[u] = true;
				// 松弛更新u连接顶点v  srci->u + u->v <  srci->v  更新
				for (size_t v = 0; v < n; ++v)
				{
					if (S[v] == false && _matrix[u][v] != MAX_W && 
						dist[u] + _matrix[u][v] < dist[v])
					{
						dist[v] = dist[u] + _matrix[u][v];
						pPath[v] = u;
					}
				}
			}
		}

		bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			size_t n = _vertexs.size();
			size_t srci = GetVertexIndex(src);

			dist.resize(n, MAX_W);
			pPath.resize(n, -1);
			// 先更新srci->srci为缺省值
			dist[srci] = W();

			// 总体最多更新n轮
			for (int k = 0;k < n; ++k)
			{
				// i->j 更新松弛
				bool update = false;
				for (int i = 0; i < n; ++i)
				{
					for (int j = 0; j < n; ++j)
					{
						// srci -> i + i ->j
						if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
						{
							update = true;
							dist[j] = dist[i] + _matrix[i][j];
							pPath[j] = i;
						}
					}
				}

				// 如果这个轮次中没有更新出更短路径，那么后续轮次就不需要再走了
				if (update == false)
				{
					break;
				}
			}

			// 还能更新就是带负权回路
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					// srci -> i + i ->j
					if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}
			return true;
		}

		void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			size_t n = _vertexs.size();
			vvDist.resize(n);
			vvpPath.resize(n);

			// 初始化权值和路径矩阵
			for (size_t i = 0; i < n; ++i)
			{
				vvDist[i].resize(n, MAX_W);
				vvpPath[i].resize(n, -1);
			}

			// 直接相连的边更新一下
			for (int i = 0; i < n; ++i)
			{
				vvDist[i][i] = W();
				for (int j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != MAX_W)
					{
						vvDist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}
				}
			}

			// 最短路径的更新i-> {其他顶点} ->j
			for (int k = 0; k < n; ++k)
			{
				for (int i = 0; i < n; ++i)
				{
					for (int j = 0; j < n; ++j)
					{
						if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
							&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];

							// 找跟j相连的上一个邻接顶点
							// 如果k->j 直接相连，上一个点就k，vvpPath[k][j]存就是k
							// 如果k->j 没有直接相连，k->...->x->j，vvpPath[k][j]存就是x
							vvpPath[i][j] = vvpPath[k][j];
						}
					}
				}

				// 打印权值和路径矩阵观察数据
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						if (vvDist[i][j] == MAX_W)
						{
							//cout << "*" << " ";
							printf("%3c", '*');
						}
						else
						{
							//cout << vvDist[i][j] << " ";
							printf("%3d", vvDist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;

				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//cout << vvParentPath[i][j] << " ";
						printf("%3d", vvpPath[i][j]);
					}
					cout << endl;
				}
				cout << "=================================" << endl;
			}
		}

	private:
		vector<V> _vertexs;			// 顶点集合
		map<V, int> _indexMap;		// 顶点映射下标
		vector<vector<W>> _matrix;	// 邻接矩阵
	};
}


namespace link_table
{
	template<class W>
	struct Edge
	{
		size_t _dsti;
		W _w;
		Edge* _next;

		Edge(size_t dsti, const W& w)
			: _dsti(dsti)
			, _w(w)
			, _next(nullptr)
		{}
	};

	template<class V, class W, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		Graph(const V* a, size_t n)
		{
			_vertexs.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				// _vertexs.push_back(a[i]);
				_vertexs[i] = a[i];
				_indexMap[a[i]] = i;
			}

			_tables.resize(n, nullptr);
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}

		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			Edge* eg = new Edge(dsti, w);
			eg->_next = _tables[srci];
			_tables[srci] = eg;

			if (Direction == false)
			{
				Edge* eg = new Edge(srci, w);
				eg->_next = _tables[dsti];
				_tables[dsti] = eg;
			}
		}

		void Print()
		{
			// 顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cout << _vertexs[i] << "[" << i << "]->";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
					cur = cur->_next;
				}
				cout << "nullptr" << endl;
			}
		}

	private:
		vector<V> _vertexs;			// 顶点集合
		map<V, int> _indexMap;		// 顶点映射下标
		vector<Edge*> _tables;		// 邻接表
	};
}